package com.coder.algorithm.leetcode;

import java.util.Stack;

public class l_0173 {

    //  Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class BSTIterator {
        private TreeNode mCur;
        private Stack<TreeNode> mStack;

        public BSTIterator(TreeNode root) {
            mCur = root;
            mStack = new Stack();
        }

        public int next() {
            while (mCur != null) {
                mStack.push(mCur);
                mCur = mCur.left;
            }
            mCur = mStack.pop();
            int ret = mCur.val;
            mCur = mCur.right;
            return ret;
        }

        public boolean hasNext() {
            return mCur != null || !mStack.isEmpty();
        }
    }

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */
}
